In packet-switched networks, a router is a network device or, in some cases, software in a computer, that determines the next network point to which a packet should be forwarded toward its destination. The router is connected to at least two networks and decides which way to send each information packet based on its current understanding of the state of the networks it is connected to. A router is located at any gateway where one network meets another and is often included as part of a network switch.
Typically, a router creates or maintains a table of the available routes and their conditions and uses this information along with distance and cost algorithms to determine the best route for a given packet. Typically, a packet may travel through a number of network points with routers before arriving at its destination. Routing is a function associated with the network layer (Layer 3) in the standard model of network programming, the Open Systems Interconnection (“OSI”) reference model.
Thus, a router is an intermediate system which operates at the network layer of the OSI reference model. Routers may be used, for example, to connect two or more Internet Protocol (“IP”) networks. In such an application, the router forwards packets from one IP network to another IP network. Such a router consists of a computer with at least two network interface cards supporting the IP protocol. The router receives packets from each interface via a network interface and forwards the received packets to an appropriate output network interface. Received packets have all link layer protocol headers removed, and transmitted packets have a new link protocol header added prior to transmission. The router uses the information held in the network layer header (i.e., the IP header) to decide whether to forward each received packet, and which network interface to use to send the packet. Most packets are forwarded based on the packet's IP destination address, along with routing information held within the router in a routing table. The routing table lists known IP destination addresses with the appropriate network interface to be used to reach that destination. A filter table may also be used to ensure that unwanted packets are discarded. The filter may be used to deny access to particular protocols or to prevent unauthorised access from remote computers by discarding packets to specified destination addresses.
A router introduces delay (i.e., latency) as it processes the packets it receives. The total delay observed is the sum of many components including: time taken to process the packet by the data link protocol; time taken to select the correct output link (i.e., filtering and routing); queuing delay at the output link (i.e., when the link is busy); and, other activities which consume processor resources (e.g., computing routing tables, network management, generation of logging information). The router's queue of packets waiting to be sent also introduces a potential cause of packet loss. Since the router has a finite amount of buffer memory to hold the queue, a router which receives packets at too high a rate may experience a full queue. In this case, the router has no other option than to discard excess packets.
As network speeds and packet processing requirements increase, corresponding improvements are required in router performance. To improve performance, routers may now include queuing devices such as network processors or traffic managers. Network processors, for example, are specialized data processing systems that are optimized to support the implementation of network protocols at the highest possible speed. A network processor typically occupies the space between a network interface and a switch fabric in a router. In such a role, the network processor decides where, when, and how incoming and outgoing data will be sent next. The network processor typically strips, adds, and modifies packet headers. It also makes routing and scheduling decisions. The network processor has interfaces to the network and to the switch fabric.
Early network processors were built around a general purpose processor (“GPP”). The GPP was supported by a direct memory access controller (“DMAC”) and simple I/O devices. Traffic was transferred in packets between memory and the switch fabric or network interface. The GPP accessed each packet and programmed the peripheral devices to dispose of it. This architecture changed as network speed outpaced processor and bus speed. The switch fabric interface and network interface were integrated into a single application-specific integrated circuit (“ASIC”) to allow packets to be transferred without passing over a system bus. This new architecture meant that control of individual packets was delegated to the ASIC. The ASIC ran hard-wired network protocols. It passed the majority of traffic through, transferring to the GPP only those packets involved in control or signalling, or those that required unusual processing. Today's network processors are designed to replace the fixed-function ASIC, adding software programmability to wire speed processing. In a typical implementation in a router, a modern network processor operates as a stage in the data plane and is controlled by a processor (e.g., a GPP) in the router operating in the control plane.
Thus, network processors manipulate packets at wire speed to implement a variety of functions including quality of service (“QoS”), encryption, firewalling, and such. These functions are often specified as network protocols, so they are implemented in protocol stacks. But network processors do not run entire protocol stacks. Protocol stacks are designed to run on GPPs and GPPs are designed—among other things—to run protocol stacks. The role of the network processor is to implement only those parts of a protocol that require direct access to the data stream. Complex behaviour is left to the GPP. The network processor's workload boils down to logically simple functionality, such as detecting packets that match specified patterns, counting packets, and enqueuing packets.
However, even with the improved performance of routers through the addition of network processors and traffic managers, router performance issues continue to exist.
A need therefore exists for an improved method and system for incorporating queuing devices such as network processors and traffic managers in network devices such as routers, switches, and gateways. Accordingly, a solution that addresses, at least in part, the above and other shortcomings is desired.